package 图.树;
import java.util.LinkedList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;
import java.util.ArrayList;

/**
 * leetcode 513 https://leetcode.cn/problems/find-bottom-left-tree-value/
 * 这个题的  一些 其他的 想法  
 * 
 *  如果  只是 简单的 层序 遍历打印  的 话 直接 
 *  可以 这样写 
 *  class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            System.out.print(root.val + " ");
            if (root.left != null) queue.offer(root.left);
            if (root.right != null) queue.offer(root.right);
        }
    }
}
这样就可以 层序打印 
但是 这样写的 缺点 是   不能 分清楚 每一层 有  多少个 节点   
所以如果 涉及 到  每层节点的处理 的话 还是 用   bfs 遍历 树的 模板 就行
 */


/**
 * 这直接 是 bfs  遍历 的 一个 模板 之一 
 * bfs 模板 ① ： dijtrasla 的  单源 最短路径 
 * 模板 ② ：  N叉树的 层序 遍历 
 * 这两 真是 经典 中的 经典 
 * bfs 的 比较透彻的 两种 用法 模板
 */


/**
 * 图.树 相关的
 * 题 就这一个 比较烦 
 * 没办法 在本地 编译 
 * 《只要思想不滑坡，方法 总比困难多》
 * 我可以直接  把 
 * leetcode 的  源码 给复制 下来 
 * main函数的 源码 
 * 《但是 又出现 了一个 问题 就是   从  leetcode 的 源码 并没 看出 他这个 图.树 是怎么 构建的
 * 而全都是 用 int 或者 Integer 代替的 ？？？？？  》
 * @author I adore you
 *
 */
public class leetcode429N叉树的层序遍历 {
	public static void main(String []args) {
		/**这个 LinkedList  还挺骚 的 说实话 
		 * 
		 * 
		 */
	Deque<Integer> queue = new	LinkedList<>();
	queue.push(1);
	queue.push(2);
	System.out.println(queue);
	int ans = queue.pollLast();
	System.out.println(ans);
	queue.offer(1);
	System.out.println(Integer.toString(21,5));
	System.out.println(Integer.parseInt("41",5));
	}
//	public static List<>
	/**
	 * 二叉树的 层序遍历
	 */
	static List<List<Integer>> solution(Node root){
		List<List<Integer>> ans = new ArrayList<>();

		/**
		 * 这里 可不能 用 泛型 Integer 了  否则   你没法进行
		 * 		Deque<Integer> q = new ArrayDeque<>();
		 */
		Deque<Node> q = new ArrayDeque<>();
		q.addLast(root);
		while(!q.isEmpty()) {
			int size  = q.size();
			List<Integer> path = new ArrayList<>();
			while(size-- > 0) {
				Node temp = q.poll();
				if(temp.left != null)
					q.addLast(temp.left);
				if(temp.right != null)
					q.addLast(temp.right);
				path.add(temp.value);
//				size --;
			}
			ans.add(path);
		}
		
		return ans ;
	}
	/**
	 * 多叉树的 一个层序 遍历 
	 * 
	 */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) 
            return ans;
        Deque<Node> q = new ArrayDeque<>();
        q.addLast(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> path = new ArrayList<>();
            while(size -- > 0){
                Node temp =  q.poll();
                for(Node cur : temp.nexts)
                    q.addLast(cur);
                path.add(temp.value);
            }
            ans.add(path);
        }
        return ans;
    }
	
}
class Node{
	int value;
	Node left;
	Node right;
	/**
	 *如果是 N 叉树的 话  
	 *那这里 是一个 List 
	 *
	 */
	List<Node> nexts ;
	public Node(int value) {
		this.value = value;
		
	}
	public Node(int value,Node left,Node right) {
		this.value = value;
		this.right = right;
		this.left = left;
	}
}
/*
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null){
            return ans;
        }
        Deque<Node> queue = new LinkedList<>();
        //if(root!= null)
        queue.push(root);
        // ans.add(new ArrayList<>().add(root.val));
        List<Integer> ro = new ArrayList<>();
        ro.add(root.val);
        ans.add(ro);
        // while(!queue.isEmpty()){
        //     Node node = queue.pollLast();
        //     List<Integer> level = new ArrayList<>();
        //     for(Node cur  : node.children){
        //         queue.push(cur.val);
        //     }
        // }
        while(!queue.isEmpty()){
            int size  = queue.size();
            List<Integer> level  = new ArrayList<>();
            for(int i = 0;i < size;i++){
                Node  node = queue.pollLast();
                for(Node cur : node.children){
                    queue.push(cur);
                    level.add(cur.val);
                } 
            }
            if(level.size() != 0){
            ans.add(new ArrayList<>(level));
            }
        }
        return ans;
    }
}
**/
